package com.lisp.algorithm.leetcode;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

import com.lisp.algorithm.util.ArrayUtil;

public class Inversion2 {

	public static void main(String[] args) {
		String s = "(ed(et(oc))el)";
		Stack<int[]> lrs = extractPInfo(s);
		StringBuilder ret = new StringBuilder();
		reverse(s, lrs, new int[] {-1, s.length()}, true, ret);
		System.out.println(ret);
	}
	
	private static void reverse(String str, Stack<int[]> lrs, int[] lastLR, 
			boolean leftToRight, StringBuilder ret) {
		if(lrs.isEmpty()) {
			String substring = str.substring(lastLR[0]+1, lastLR[1]);
			if(leftToRight) {
				ret.append(substring);
			} else {
				ret.append(new StringBuilder(substring).reverse());
			}
		} else {
			int[] currentLR = lrs.pop();
			String leftPart = str.substring(lastLR[0]+1, currentLR[0]);
			String rightPart = str.substring(currentLR[1]+1, lastLR[1]);
			if(leftToRight) {
				ret.append(leftPart);
				reverse(str, lrs, currentLR, !leftToRight, ret);
				ret.append(rightPart);
			} else {
				ret.append(new StringBuilder(rightPart).reverse());
				reverse(str, lrs, currentLR, !leftToRight, ret);
				ret.append(new StringBuilder(leftPart).reverse());
			}
		}
	}
	
	private static Stack<int[]> extractPInfo(String str) {
		Stack<int[]> ret = new Stack<int[]>();
		Stack<Integer> s = new Stack<Integer>(); 
		for(int i=0, len=str.length(); i<len; i++) {
			char ch = str.charAt(i);
			if(ch == '(') {
				s.push(i);
			} else if(ch == ')') {
				int[] leftRight = new int[] {s.pop(), i};
				ret.push(leftRight);
			}
		}
		return ret;
	}
}
